package com.lun.hard;

import com.lun.util.BinaryTree.TreeNode;

public class BinaryTreeMaximumPathSum {
    
	private static int MIN_VALUE = -1001;//不用Integer.MIN_VALUE，原因是用它可能造成溢出情况
	
	//方法一：我写的
	public int maxPathSum(TreeNode root) {
    	int[] maxAlone = {MIN_VALUE};
    	int max = maxPathSum(root, maxAlone);
    	return Math.max(maxAlone[0], max);
    }
    
    private int maxPathSum(TreeNode node, int[] maxAlone) {
    	if(node == null) return MIN_VALUE;
   
    	int leftMax = maxPathSum(node.left, maxAlone);
    	int rightMax = maxPathSum(node.right, maxAlone);

    	int maxOne = Math.max(Math.max(leftMax, rightMax), //
    			leftMax + rightMax + node.val); 
    	
    	if(maxOne > maxAlone[0]) {
    		maxAlone[0] = maxOne;
    	}
    	
    	return Math.max(Math.max(leftMax + node.val, rightMax + node.val),// 
    			node.val);
    }
	
	//方法二：别人写的
	public int maxPathSum2(TreeNode root) {
    	int[] max = {Integer.MIN_VALUE};
    	maxPathSum2(root, max);
    	return max[0];
    }
    
    private int maxPathSum2(TreeNode node, int[] max) {
        if (node == null) return 0;
        //如果节点值是负数，那么干脆不采用这节点值，也就是用0代替这节点值（如节点值为-9，它的父节点为n，n+(-9) < n + 0
        int leftMax = Math.max(0, maxPathSum2(node.left, max));
        int rightMax = Math.max(0, maxPathSum2(node.right, max));
        max[0] = Math.max(max[0], leftMax + rightMax + node.val);
        return Math.max(leftMax, rightMax) + node.val;
    }
    
}
